package cmlabs.numbertheoryutils.algorithms;

import cmlabs.numbertheoryutils.Functions;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * Created by IntelliJ IDEA.
 * User: jte
 * Date: 9.4.11
 * Time: 18.23
 * To change this template use File | Settings | File Templates.
 */
public class PrimeNumbers {

    public static boolean isPrime(long candidate, int percentOfError) {
        if ((candidate & 1) == 0)
            return false;
        if (candidate <= trivialMax) {
            return Arrays.binarySearch(trivialPrimes, candidate) != -1;
        }
        long t = candidate - 1, r = 0;
        while ((t & 1) == 0) {
            r++;
            t >>= 1;
        }
        List<Long> degrees = new ArrayList<Long>();
        for (int i = 1; i <= r; ++i) {
            degrees.add((candidate - 1) >> i);
        }
        for (int i = 0; i < percentOfError; ++i) {
            Random current = new Random(System.currentTimeMillis());
            long a = current.nextLong() % candidate;
            boolean result = cmlabs.numbertheoryutils.Functions.powMod(a, t, candidate) == 1;
            if (!result) {
                result = true;
                for (long exp : degrees) {
                    result &= cmlabs.numbertheoryutils.Functions.powMod(a, exp, candidate) == candidate - 1;
                }
                if (!result) {
                    return false;
                }
            }
        }
        return true;
    }

    public static long generatePrime(int bitLength) {
        if (bitLength > 62) {
            throw new IllegalArgumentException("MAX BITS = 62");
        }
        return BigInteger.probablePrime(bitLength, new Random(System.currentTimeMillis())).longValue();
    }

    private static final long trivialMax = (long) 1e8;
    private static final Integer[] trivialPrimes = Functions.getPrimes((int) trivialMax);
}
